public class EditDistance {
    public int editDistance (String str1, String str2) {
        // write code here
        // dp[i][j]表示str1[0,i],str2[0,j]之间的最少操作数
        // 对于str1.charAt(i), str2.charAt(j)有以下几种操作
        // 1.删除str1第i个字符 2.增加str1 i+1位置为str2的第j个字符 3.修改str1第i个字符
        // 4.删除str2第j个字符 5.增加str2 j+1位置为str1的第i个字符 6.修改str2第j个字符
        // 然后上面的六种情况可以合并为下面几种情况
        // 1.删除str1第i个字符 2.删除str2第j个字符 3.修改第i个字符
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i-1) != str2.charAt(j-1)) {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                } else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        EditDistance edit = new EditDistance();
        System.out.println(edit.editDistance("abcnowcoder", "new"));
    }
}
